"""
例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。
排列组合思想：m-1+n-1步其中有n-1步向下
Cm+n-2 n-1
"""
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        s = m-1+n-1
        c = n-1
        mf = 1
        mn = 1
        for i in range(c+1,s+1):
            mf = mf*i
        for i in range(1, s-c+1):
            mn = mn*i
        return mf//mn

s=Solution()
print(s.uniquePaths(7,3))